A common problem in engineering is the design of a device whose operation is governed by physical phenomena too complex or whose shape is too irregular for a closed-form analytical expression describing its behavior to be developed. In these cases, it is typical for a finite element or finite volume approximation to be created by decomposing the geometric shape of the device and/or the space around the device into a number of primitive shapes over which a simple analytical form is used to approximate some quantity of interest (e.g., stress, strain, temperature). These primitive shapes may be simplices such as lines, triangles, or tetrahedra; or non-simplicial polytopes such as quadrilaterals, hexahedra, pyramids, wedges, or knives. While the analytical forms defined over each primitive are simple, their combination may exhibit complex patterns that closely approximate the solution to some engineering problem. Unfortunately, if the decomposition of the geometry into primitives is too coarse in some regions, the variations allowed by the analytical forms may not approximate the solution well, for example, the behavior of a region at the end of a narrow projection of a machine tool subjected to rapid, inelastic strain.
In these situations, it is desirable to refine the original decomposition in regions where primitives are too coarse. This is easily accomplished with simplicial primitives but not with other primitives because there are no algorithms that automatically create meshes from a boundary specification; this is still typically performed with human assistance. The refinement process must preserve two important properties of meshes to be useful for most simulation techniques.
One of the properties that refinement schemes must preserve is mesh conformality. A mesh of n-dimensional polytopes is conformal if every (n−1)-boundary (face for n=3) of a primitive is shared with at most one neighboring primitive. Furthermore, when an (n−1)-boundary is shared, it must be defined identically by both neighboring primitives; every point on the shared (n−1)-boundary of one primitive must appear on the corresponding shared (n−1)-boundary of the neighbor. Conformal meshes are called complexes.
Refinement schemes must also preserve—or at least gracefully degrade—the geometric quality of the primitives that compose the mesh. There are many different measures of geometric quality, but perhaps the minimum requirement is that: assuming all input primitives are convex then all output primitives shall be convex. Convexity is an important property in finite-element simulations because, for typical parameterizations of primitive polytopes, concavity implies that the Jacobian is negative inside the element. The geometric Jacobian appears in the quadrature formulation used to determine values of scalar, vector, and tensor fields and a negative Jacobian incorrectly weights the contribution of a region of the element to the whole, usually resulting in a divergent simulation.
Besides preserving properties of the mesh, any refinement scheme also requires a way for a simulation to indicate which regions require refinement. In 3-dimensional simplicial (i.e., tetrahedral) refinement schemes, this is typically accomplished by defining a target edge size at vertices (vertex-based refinement); by indicating a set of edges to be subdivided (edge-based refinement); or by indicating a set of faces to be subdivided (face-based refinement). We have shown (Pébay, P. P. and Thompson, D., “Communication-free streaming mesh refinement,” Journal of Computing and Information Science in Engineering, 2005, v.5(4): pp. 309-316; and Thompson, D. and Pébay, P. P., “Embarrassingly parallel streaming mesh refinement,” Engineering and Computers, 2006, v.22(2): pp. 75-93, 13th International Meshing Roundtable) how tetrahedral edge-based refinement can be performed in parallel with little or no communication—depending on whether vertices shared between processes need to be cross-referenced.